package love_map

import "sort"

//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
//
//注意： 答案中不可以包含重复的三元组。
//
//示例：
//
//给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//
//满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

func TreeSum(nums []int) [][]int {
	sort.Ints(nums)

	re := [][]int{}
	k := 0
	left := 1
	right := len(nums) - 1
	for k < right-1 {

		if k > 0 && nums[k] == nums[k-1] {
			k++
			left = k + 1
			right = len(nums) - 1
			continue
		}

		for left < right {
			if nums[left]+nums[right]+nums[k] > 0 {
				right--
			} else if nums[left]+nums[right]+nums[k] < 0 {
				left++
			} else if nums[left]+nums[right]+nums[k] == 0 {
				re = append(re, []int{nums[k], nums[left], nums[right]})
				left++
				right--
			}
		}
		k++
		left = k + 1
		right = len(nums) - 1
	}
	return re
}

//重点：
//排序-也方便去重
// 三个指针，left 根据 k 移动+1，left的移动
//等于0时，left right全部移动可中和
//复杂度n的平方
//还是去重去重k重复
